題目來源:Add Two Number
問題:
給予兩個 linked lists, 並且在 linked list 裡的所有元素都是正數(沒有負數)而且都是個位數 ,請試著將兩個 linked list 中的數字個別相加到另一個 linked list,若相加超過各位數則進位下至一個節點。
ListNode 定義
public class ListNode {
public int val {get; set;}
public ListNode next {get; set;}
public ListNode(int value){
this.val = value
next = null;
}
}
例子
輸入:linked list1: 2 -> 4 -> 3 ; linked list2: 5-> 6-> 4
輸出:7 -> 0-> 8
因為第二個節點 4 + 6 剛好等於 10,所以進位到下一個節點。因此在處理下一個節點時就會多一個進位過來的數字
3 (linked list 1)+ 4(linked list 2) + 1( 第二節點的進位)
想法
兩個 linked list 的節點相加、進位,乍看之下好像很容易,但第一次做起來卻又一堆問題!
我覺得那因為題目沒說兩個 linked list 的節點數目是否相同,所以這兩種可能都必需要考慮進去。否則就會過不了 test case。
因此,我覺的關於這一題的重點應該是計算兩 linked list相加的中止條件。
那麼中止條件是什麼呢?那就要想題目要求什麼?題目給的限制是:
所以兩兩相對應節點相加有值產生可能會遇到情況有
那不可能會有值得情況應該是:
所以根據上面的判斷,我們的中止條件應該是:
Linked list1 的節點 或 Linked list 2 的節點 或 進位的值 皆為 null
換句話說 [ (Linked list1 Node != null) 或 (LinkedList 2 Node != null) 或 (進位值 != 0 ) ]
因此,找到中止條件之後,整個題目就會變得很簡單了,接下來所要的事情就是兩兩相加了!!
虛擬碼
當 ( **節點1 不等於 null** 或 **節點 2 不等於 null** 或 **進位值 不等於 0**)
節點1+節點2+進位值 assign 給 sum
從 sum 取得各位數和十位數
在回傳的 linked list 上新增一節點並且給值為剛取得的 **個位數**
將剛取得的十位數暫存在 **進位值** 上
取得節點1的下一個節點 並 assign 給節點1
取得節點2的下一個節點 並 assign 給節點2
如果你用 Java or Python or C++ 可上 [LeetCode Online Judge][Problem] 驗證
還是想不出來嗎?參考我的答案吧!
// C# 版本
public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
ListNode dummy = new ListNode(0);
ListNode node = dummy;
int digitInTens = 0;
while (list1Node != null || list2Node != null || digitInTens != 0)
{
int sum = 0;
if (list1Node != null && list2Node != null)
sum = list1Node.val + list2Node.val + digitInTens;
else if (list1Node != null)
sum = list1Node.val + digitInTens;
else if (list2Node != null)
sum = list2Node.val + digitInTens;
else
sum = digitInTens;
int digitInOnes = sum % 10;
digitInTens = sum / 10;
node.next = new ListNode(digitInOnes);
node = node.next;
if (list1Node == null)
list1Node = null;
else
list1Node = list1Node.next;
if (list2Node == null)
list2Node = null;
else
list2Node = list2Node.next;
}
return dummy.next;
}
題外話,雖然寫完了但是程式碼實在太醜了,也很難看得懂,我們來 Refactor 一下吧!
首先呢,先幫程式碼加個註解,以方便抽取我們想要的部份
// 加註解的結果
public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
ListNode dummy = new ListNode(0);
ListNode node = dummy;
int digitInTens = 0;
while (list1Node != null || list2Node != null || digitInTens != 0)
{
// 兩個 Linked list 節點相加
int sum = 0;
if (list1Node != null && list2Node != null)
sum = list1Node.val + list2Node.val + digitInTens;
else if (list1Node != null)
sum = list1Node.val + digitInTens;
else if (list2Node != null)
sum = list2Node.val + digitInTens;
else
sum = digitInTens;
// 取得個位數
int digitInOnes = sum % 10;
// 取得十位數
digitInTens = sum / 10;
// 將個位數新增到結果的 linked list 上
node.next = new ListNode(digitInOnes);
node = node.next;
// linked list 1 取得下一個節點
if (list1Node == null)
list1Node = null;
else
list1Node = list1Node.next;
// linked list 2 取得下一個節點
if (list2Node == null)
list2Node = null;
else
list2Node = list2Node.next;
}
return dummy.next;
}
加註解後,就依照各部份使用 Extract Method
取出來吧,讓我們住要的程式碼能夠在同一個表達層級上。
// extract method 後的結果
public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
ListNode dummy = new ListNode(0);
ListNode node = dummy;
int digitInTens = 0;
while (list1Node != null || list2Node != null || digitInTens != 0)
{
int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;
int digitInOnes = GetDigitInOnes(sum);
digitInTens = GetDigitInTens(digitInTens, sum);
node = AddSumToResultLinkedListNode(node, digitInOnes);
list1Node = GetNextNode(list1Node);
list2Node = GetNextNode(list2Node);
}
return dummy.next;
}
private static ListNode GetNextNode(ListNode node)
{
// 取得下一個節點
if (node == null)
node = null;
else
node = node.next;
return node;
}
private static ListNode AddSumToResultLinkedListNode(ListNode node, int digitInOnes)
{
// 將個位數新增到結果的 linked list 上
node.next = new ListNode(digitInOnes);
node = node.next;
return node;
}
private static int GetDigitInTens(int digitInTens, int sum)
{
// 取得十位數
digitInTens = sum / 10;
return digitInTens;
}
private static int GetDigitInOnes(int sum)
{
// 取得個位數
int digitInOnes = sum % 10;
return digitInOnes;
}
private static int CalculateTwoNodeSum(ListNode list1Node, ListNode list2Node)
{
// 兩個 Linked list 節點相加
int sum = 0;
if (list1Node != null && list2Node != null)
sum = list1Node.val + list2Node.val;
else if (list1Node != null)
sum = list1Node.val;
else if (list2Node != null)
sum = list2Node.val;
else
sum = 0;
return sum;
}
有沒有覺的,主要的程式碼變得非常清晰了呢?別忘了在每做一次 Extract Method
後,要跑一下 **Unit Test** 以確保程式沒被改壞掉。 如果你有潔癖的話,還可以繼續處理抽出來的程式碼:
// 完成重構的程式碼,真乾淨
public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
ListNode dummy = new ListNode(0);
ListNode node = dummy;
int digitInTens = 0;
while (list1Node != null || list2Node != null || digitInTens != 0)
{
int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;
int digitInOnes = GetDigitInOnes(sum);
digitInTens = GetDigitInTens(digitInTens, sum);
node = AddSumToResultLinkedListNextNode(node, digitInOnes);
node = GetNextNode(node);
list1Node = GetNextNode(list1Node);
list2Node = GetNextNode(list2Node);
}
return dummy.next;
}
private static ListNode GetNextNode(ListNode node)
{
// 取得下一個節點
return (node == null) ? null : node.next;
}
private static ListNode AddSumToResultLinkedListNextNode(ListNode node, int digitInOnes)
{
// 將個位數新增到結果的 linked list 上
node.next = new ListNode(digitInOnes);
return node;
}
private static int GetDigitInTens(int digitInTens, int sum)
{
// 取得十位數
return sum / 10;
}
private static int GetDigitInOnes(int sum)
{
// 取得個位數
return sum % 10;
}
private static int CalculateTwoNodeSum(ListNode list1Node, ListNode list2Node)
{
// 兩個 Linked list 節點相加
int sum = GetListNodeValue(list1Node) + GetListNodeValue(list2Node);
return sum;
}
private static int GetListNodeValue(ListNode node)
{
if (node != null)
return node.val;
return 0;
}
哈哈!似乎有點太過分了!!不過,有沒有注意到我的 if - else
都快被我抽光光的!我認為好的程式碼品質就是要項這樣,跟文章一樣讀起來很輕鬆、很愉快!但前提是必序要有 **足夠的** test case, 不然這樣抽,可能一不小心就把城市給搞壞了!!
最後再回顧一下,這時候如果再替程式碼加上註解,是不視覺的有點雞肋了呢?
// 有點雞肋的註解
while (list1Node != null || list2Node != null || digitInTens != 0)
{
// 兩節點值相加並 加上前一節點的進位值
int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;
// 取得個位數
int digitInOnes = GetDigitInOnes(sum);
// 取得十位數
digitInTens = GetDigitInTens(digitInTens, sum);
// 將相加的個位數新增至相加結果的 LinkedList
node = AddSumToResultLinkedListNextNode(node, digitInOnes);
node = GetNextNode(node);
// 取得兩 linked list 的下一節點
list1Node = GetNextNode(list1Node);
list2Node = GetNextNode(list2Node);
}